﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using CharmL.Helper;


namespace CharmL {
    public class CLICL {
        public LatticeNode L { get; set; }
        public IndexTable FirstNodes { get; set; }

        public CLICL() {
            L = new LatticeNode();
            FirstNodes = new IndexTable();
        }

        //public void InitLattice(int tid, List<int> t) {
        //    //the first itemset            
        //    Concept root = new Concept();
        //    root.ID = 0;
        //    L.AddConceptWithID(root);
        //    L.RootNodeID = 0;
        //    root.Tids.AddUnique(1);


        //    Concept lastNode = new Concept();
        //    lastNode.ID = 0;
        //    lastNode.Items = t;
        //    L.AddConcept(lastNode);
        //    L.LastNodeID = 1;

        //    Concept firstNode = new Concept();
        //    firstNode.ID = 1;
        //    firstNode.Items = t;
        //    firstNode.Tids.AddUnique(1);
        //    L.AddConcept(firstNode);

        //    root.AddChild(firstNode);
        //    firstNode.AddChild(lastNode);

        //    foreach (int item in t) {
        //        FirstNodes.AddIndex(item, 2);
        //    }
        //}
        ////Build Base lattice

        ////Delete transaction

        //internal void AddTransaction(List<int> itemSet) {
        //    throw new NotImplementedException();
        //}

        ///// <summary>
        ///// Add transaction to the current Lattice L 
        ///// </summary>
        ///// <param name="tid">transaction id</param>
        ///// <param name="t">item set of the transaction to insert</param>        
        //public void AddTransaction(int tid, List<int> t) {
        //    //update lastNode
        //    //L.Concepts[L.LastNodeID].Items = L.Concepts[L.LastNodeID].Items.UnionWith(t);
        //    ////update root node
        //    //L.Concepts[L.RootNodeID].Tids.AddUnique(tid);
        //    LatticeNode temp = ItemSetIsExistedInLattice(t);
        //    //if (temp != null) {
        //    //    temp.Tids.AddUnique(tid);
        //    //    //Console.WriteLine("add {0} to concept {1}", tid, tid);
        //    //    return;
        //    //}



        //    //create a new Node N with In = t
        //    AddTransaction(new List<int>() { tid }, t);
        //}

        public LatticeNode AddTransaction(int sup, List<int> items, MaximalTest maximal) {
            LatticeNode temp = ItemSetIsExistedInLattice(items);
            if (temp != null) {
                temp.Sup++;
                UpdateSupport(temp,  false);

                return temp;
            }
            LatticeNode n = new LatticeNode();
            n.Items = items;
            n.Sup = sup;
            List<LatticeNode> checkedItemIndex = new List<LatticeNode>();

            bool isAdded = false;
            //for all item i in t in L do
            foreach (int i in items) {
                LatticeNode fi = FirstNodes.GetFirstNode(i);
                if (fi == null) {
                    //never
                    if (isAdded) {
                        FirstNodes.AddIndex(i, n);
                    }
                    continue;
                }

                if (checkedItemIndex.Contains(fi)) {
                    continue;
                }

                checkedItemIndex.Add(fi);

                //if Fi is ancestor of N then (this is the common case)
                if (fi.Items.IsAncestorOf(n.Items)) {
                    //always
                    //find child and parents of N among the descendants of fi
                    Case1(n, fi, ref isAdded, sup, maximal);
                } else if (fi.Items.IsDescendantOf(n.Items)) {
                    //if Fi is descendant of N 
                    //child of N is Fi and parents of N are among the ancestors of fi
                    Case2(n, fi, i, ref isAdded, sup, maximal);

                } else {
                    Case3(n, fi, i, ref isAdded, sup, maximal);
                }
            }
            if (!isAdded) {
                maximal.lattice.Add(n);
            }

            foreach (int item in items) {
                if (!FirstNodes.ContainsKey(item)) {
                    FirstNodes.AddIndex(item, n);
                }
            }
            //update sup
            UpdateSupport(n, true);
            return n;
        }

        private void UpdateSupport(LatticeNode n,  bool calCurNodeSup) {
            if (calCurNodeSup) {
                int max = n.Sup;
                if (n.Child != null && n.Child.Count > 0) {
                    if (n.Child.Count == 1 && n.Sup == 1) {
                        //n has only one child and n is new node => support of n = support of child + 1
                        n.Sup = n.Child[0].Sup + 1;
                    } else {
                        
                        foreach (LatticeNode item in n.Child) {
                            if (item.Sup > max) {
                                max = item.Sup;
                            }
                        }
                        n.Sup = max + 1;
                    }
                }
            }

            HashSet<LatticeNode> nodes = new HashSet<LatticeNode>();
            foreach (LatticeNode item in n.Parent) {
                UpdateSupport(item, nodes);
            }

            foreach (LatticeNode item in nodes) {
                item.Sup++;
            }            
        }

        private void UpdateSupport(LatticeNode n, HashSet<LatticeNode> nodes) {

            nodes.Add(n);
            foreach (LatticeNode item in n.Parent) {
                //nodes.Add(item);
                UpdateSupport(item, nodes);
            }

        }
        #region Case 3 - New
        private void Case3(LatticeNode n, LatticeNode fi, int i, ref  bool isAdded, int sup, MaximalTest maximal) {
            //if common parent X of Fi and N exist in L then
            //  parent of N is X and child of N is among descendants of fi
            //else
            //  create a new node X where Ix = Ifi and In
            //  parent of N is X and child of N is among descendants of Fi
            //  children of X are fi and some ancestor of N
            //  parents of X are among the ancestors of fi
            //  if X is neither ancestor nor descendant of node Y thuoc L and Ix and Iy khac rong
            //  then
            //      create a new node U such that Iu = Iy and Ix
            //      find child and parents of node U
            //  end if
            //end if

            //Case 3: Fi is neither ancestor nor descendent of N.  (Ifi not in In, Ifi not cover In, Ifi /\ In <> null)
            //In this case, common parent of Fi and N with closed itemset as X = Ifi /\ In may exists in L or it may not exist
            if (!isAdded) {
                //L.AddConcept(n);
                maximal.lattice.Add(n);
                isAdded = true;
            }

            LatticeNode x = new LatticeNode();
            x.Items = fi.Items.IntersectWith(n.Items);
            //Concept x = new Concept();
            //x.Items = fi.Items.IntersectWith(n.Items);

            LatticeNode t = ItemSetIsExistedInLattice(x.Items);

            //Concept t = ItemSetIsExistedInLattice(x.Items);
            //List<int> tids = fi.Tids.UnionWith(n.Tids);


            //Case 3.1: Ifi /\ In exists as closed itemset of a node X in L
            //If such a node X existed in L then 
            //  X is parent of N. 
            //  Child of N is among the descendants of Fi. We check all the descendants of Fi till we find a node
            //      whose closed itemset is minimal superset of closed itemset of N, that node becomes the child of N
            if (t != null) {
                Case3_1(n, fi, t, i, sup);
            } else {
                ////Case 3.2: Ifi /\ In does not exists as closed itemset of a node X in L
                ////A new node X is created with Ix = Ifi /\ In and added to L. 
                ////  X becomes the parent of N 
                ////  and child of N is among the descendants of Fi.
                ////      We check all the descendants of Fi till we get a node
                //          those closed itemset is minimal superset of closed itemset of N, that node becomes the child of N.
                //x.Tids = tids;
                x.Sup = fi.Sup;
                Case3_2_1_FindParentAndChildOfXInDescendantsOfFi(n, fi, x, sup, maximal);

                ////Next step is to find the child and parents of X.
                ////  Parents of X are among the ancestors of Fi
                ////      We check all the ancestors of Fi. If we get a node Y such that 
                ////          closed itemset of Y is superset of X 
                ////          and closed itemset of one of the parent Z of Y is subset of X
                ////          then Z becomes the parent of X
                ////          and Y is child of X
                ////  If we find an ancestor Y of Fi such that Y is neither ancestor nor descendent of X, then
                ////      a new node U is created with Iu = Iy /\ Ix.
                ////      Then we repeat the process to find child and parents of node U 
                x.AddChild(fi);

                FirstNodes.UpdateIndexIfExisted(i, x, fi);
                List<LatticeNode> checkedConceptIds = new List<LatticeNode>();
                List<LatticeNode> notParentIds = new List<LatticeNode>();
                List<LatticeNode> notChildIds = new List<LatticeNode>();
                bool isFind = false;

                Case3_2_2_FindChildAndParentOfXInAncestorFi(x, fi, checkedConceptIds, notParentIds, notChildIds, sup, ref isFind, maximal);
                ////Case3_2_2_Wrong(x, fi, fi, i);
            }
        }


        private void Case3_2_2_FindChildAndParentOfXInAncestorFi(LatticeNode n, LatticeNode currentNode, List<LatticeNode> checkedConceptIds, List<LatticeNode> notParentIds, List<LatticeNode> notChildIds, int sup, ref bool isFind, MaximalTest maximal) {
            if (isFind || checkedConceptIds.Contains(currentNode)) { return; }
            //foreach (LatticeNode parent in currentNode.Parent) {
            for (int parentIndex = 0; parentIndex < currentNode.Parent.Count; parentIndex++) {

                LatticeNode parent = currentNode.Parent[parentIndex];
                if (checkedConceptIds.Contains(parent) || n == parent) { continue; }
                //Concept parent = L.Concepts[parentID];
                bool isNotInChild = notChildIds.Contains(parent);
                if (isNotInChild) {
                    //notChildIds = notChildIds.UnionWith(parent.ChildrenID);
                    notChildIds.AddRange(parent.Child);
                }

                SubSetRes res = parent.SubSet(n);
                bool isSuperSet = (res == SubSetRes.SUPSET);  //parent.Items.IsSuperSetOf(n.Items);

                if (!isNotInChild && isSuperSet) {
                    //all parents of parent isn't superset of x => add parent as x parent
                    bool noParentOfParentIsSuperSet = true;
                    bool needLoop = true;


                    //foreach (LatticeNode parentOfParent in parent.Parent) { //.GetParentID()) {
                    for (int parentOfParentIndex = 0; parentOfParentIndex < parent.Parent.Count; parentOfParentIndex++) {

                        LatticeNode parentOfParent = parent.Parent[parentOfParentIndex];
                        //if (n.ID == parentOfParentID) { continue; }
                        if (n == parentOfParent) { continue; }
                        //Concept parentOfParent = L.Concepts[parentOfParentID];
                        if (notChildIds.Contains(parentOfParent)) {
                            //notChildIds = notChildIds.UnionWith(parentOfParent.ChildrenID);
                            notChildIds.AddRange(parentOfParent.Child);
                            continue;
                        }

                        if (parentOfParent.Items.IsSuperSetOf(n.Items)) {
                            noParentOfParentIsSuperSet = false;
                            //notChildIds.Add(parentID);
                            notChildIds.Add(parent);
                            break;
                        } else {
                            //bool isNotInParent1 = notParentIds.Contains(parentOfParentID);
                            bool isNotInParent1 = notParentIds.Contains(parentOfParent);
                            if (isNotInParent1) {
                                //notParentIds = notParentIds.UnionWith(parentOfParent.ChildrenID);
                                notChildIds.AddRange(parentOfParent.Child);
                            }
                            if (!isNotInParent1 && parentOfParent.Items.IsSubSetOf(n.Items)) {
                                //remove connection between child and childOfChild
                                parent.RemoveParentBiDirection(parentOfParent);
                                parentOfParentIndex--;
                                //parent.AddParent(n);
                                n.AddChild(parent);

                                //n.AddParent(parentOfParent);
                                parentOfParent.AddChild(n);

                                //checkedConceptIds.AddUnique(parentOfParent.ID);
                                checkedConceptIds.Add(parentOfParent);
                                //checkedConceptIds.AddUnique(parent.ID);                                
                                checkedConceptIds.Add(parent);
                            }
                        }

                    }
                    if (noParentOfParentIsSuperSet) {
                        //=> parent is superSet of x
                        //parent.AddParent(n);
                        n.AddChild(parent);

                        //notChildIds = notChildIds.UnionWith(parent.ChildrenID);
                        //notChildIds.AddUnique(parentID);

                        notChildIds.AddRange(parent.Child);
                        notChildIds.Add(parent);
                        //notParentIds = notParentIds.UnionWith(parent.ChildrenID);
                        //notParentIds.AddUnique(parentID);
                        notParentIds.AddRange(parent.Child);
                        notParentIds.Add(parent);
                        //checkedConceptIds.AddUnique(parent.ID);
                        checkedConceptIds.Add(parent);
                    }
                    if (needLoop) {
                        Case3_2_2_FindChildAndParentOfXInAncestorFi(n, parent, checkedConceptIds, notParentIds, notChildIds, sup, ref isFind, maximal);
                    }
                }

                bool isSubSet = (res == SubSetRes.SUBSET); //parent.Items.IsSubSetOf(n.Items);
                bool isInNotParent = notParentIds.Contains(parent);
                if (isInNotParent) {
                    //notParentIds = notParentIds.UnionWith(parent.ParentID);
                    notParentIds.Add(parent);
                }
                if (!isInNotParent && isSubSet) {
                    //n.AddParent(parent);
                    parent.AddChild(n);

                    //notChildIds = notChildIds.UnionWith(parent.ParentID);
                    //notChildIds.AddUnique(parentID);
                    notChildIds.AddRange(parent.Parent);
                    notChildIds.Add(parent);
                    //notParentIds = notParentIds.UnionWith(parent.ParentID);
                    //notParentIds.AddUnique(parentID);
                    notParentIds.AddRange(parent.Parent);
                    notParentIds.Add(parent);
                    //checkedConceptIds.AddUnique(parentID);
                    checkedConceptIds.Add(parent);

                    //foreach (int childOfParentID in parent.GetChildrentID()) {
                    //foreach (LatticeNode childOfParent in parent.Child) {
                    for (int childOfParentIndex = 0; childOfParentIndex < parent.Child.Count; childOfParentIndex++) {

                        LatticeNode childOfParent = parent.Child[childOfParentIndex];
                        if (n == childOfParent) { continue; }
                        // Concept childOfParent = L.Concepts[childOfParentID];
                        bool isNotInChild1 = notChildIds.Contains(childOfParent);
                        if (isNotInChild1) {
                            //notChildIds = notChildIds.UnionWith(childOfParent.ParentID);
                            notChildIds.AddRange(childOfParent.Parent);
                        }
                        if (!isNotInChild1 && childOfParent.Items.IsSuperSetOf(n.Items)) {
                            childOfParent.RemoveParentBiDirection(parent);
                            childOfParentIndex--;
                            //childOfParent.AddParent(n);
                            //n.AddParent(parent);
                            n.AddChild(childOfParent);
                            parent.AddChild(n);
                            //checkedConceptIds.AddUnique(parentID);
                            //checkedConceptIds.AddUnique(childOfParentID);
                            checkedConceptIds.Add(parent);
                            checkedConceptIds.Add(childOfParent);
                        }
                    }
                    if (sup == 1) { isFind = true; return; }
                    //if (tidCount == 1) { isFind = true; return; }
                }
                if (!isSuperSet && !isSubSet) {
                    //Concept newNode = new Concept();
                    LatticeNode newNode = new LatticeNode();
                    //newNode.Items = n.Items.IntersectWith(parent.Items);
                    newNode.Items = n.Items.IntersectWith(parent.Items);
                    newNode.Sup = n.Sup > parent.Sup ? n.Sup : parent.Sup;
                    LatticeNode existedNode = ItemSetIsExistedInLattice(newNode.Items);
                    //if (newNode.Items.Count > 0 && existedNode == null) {
                    //    AddTransaction(n.Tids.UnionWith(parent.Tids), newNode.Items);
                    //} else if (existedNode != null) {
                    //    n.AddParent(existedNode);
                    //    checkedConceptIds.Add(existedNode.ID);
                    //}

                    if (newNode.Items.Count > 0 && existedNode == null) {
                        AddTransaction(parent.Sup, newNode.Items, maximal);
                    } else if (existedNode != null) {
                        existedNode.AddChild(n);
                        checkedConceptIds.Add(existedNode);
                    }
                }


            }

        }

        private void Case3_2_1_FindParentAndChildOfXInDescendantsOfFi(LatticeNode n, LatticeNode fi, LatticeNode x, int sup, MaximalTest maximal) {
            //Case 3.2: Ifi /\ In does not exists as closed itemset of a node X in L
            //A new node X is created with Ix = Ifi /\ In and added to L. 
            //  X becomes the parent of N 
            //  and child of N is among the descendants of Fi.
            //      We check all the descendants of Fi till we get a node
            //          those closed itemset is minimal superset of closed itemset of N, that node becomes the child of N.
            //L.AddConcept(x);
            maximal.lattice.Add(x);

            for (int parentIndex = 0; parentIndex < n.Parent.Count; parentIndex++) {
                LatticeNode parent = n.Parent[parentIndex];
                if (parent.SubSet(x) == SubSetRes.SUBSET) {
                    n.RemoveParentBiDirection(parent);
                    //we don't metion what is x parent now!!!
                }
            }
            //foreach (LatticeNode parent in n.Parent) {
            //    //if (parent.Items.IsSubSetOf(x.Items)) {
            //    if (parent.SubSet(x) == SubSetRes.SUBSET) {
            //        n.RemoveParentBiDirection(parent);
            //        //we don't metion what is x parent now!!!
            //    }
            //}
            //n.AddParent(x);
            x.AddChild(n);
            bool isFind = false;
            List<LatticeNode> checkedItems = new List<LatticeNode>();
            Case3_1_FindChildOfNInDescendantsOfFi(n, fi, sup, ref isFind, checkedItems);
        }

        private void Case3_1(LatticeNode n, LatticeNode fi, LatticeNode x, int i, int sup) {
            //Case 3.1: Ifi /\ In exists as closed itemset of a node X in L
            //If such a node X existed in L then 
            //  X is parent of N. 
            //  Child of N is among the descendants of Fi. We check all the descendants of Fi till we find a node
            //      whose closed itemset is minimal superset of closed itemset of N, that node becomes the child of N

            //n.AddParent(x);
            x.AddChild(n);
            //
            FirstNodes.UpdateIndexIfExisted(i, x, fi);
            if (x.Child.Count == 0) {
                //in this case, x is parent of lower node => so now n is parent of lower node
                return;
            }
            //Case3_1_FindChildOfNInDescendantsOfFi(tid, n, fi);

            for (int desFiIndex = 0; desFiIndex < fi.Child.Count; desFiIndex++) {

                LatticeNode desFi = fi.Child[desFiIndex];
                bool isFind = false;
                List<LatticeNode> checkedItems = new List<LatticeNode>();
                Case3_1_FindChildOfNInDescendantsOfFi(n, desFi, sup, ref isFind, checkedItems);
                //Case3_1_FindChildOfNInDescendantsOfFi(n, desFi);

            }
            //foreach (LatticeNode desFi in fi.Child) {
            //bool isFind = false;
            //List<LatticeNode> checkedItems = new List<LatticeNode>();
            //Case3_1_FindChildOfNInDescendantsOfFi(n, desFi, sup, ref isFind, checkedItems);
            ////Case3_1_FindChildOfNInDescendantsOfFi(n, desFi);
            //}

        }

        private void Case3_1_FindChildOfNInDescendantsOfFi(LatticeNode n, LatticeNode currentNode, int tidCount, ref bool isFind, List<LatticeNode> checkedItem) {
            if (isFind) return;
            if (checkedItem.Contains(currentNode)) {
                checkedItem.Add(currentNode);
                //checkedItem = checkedItem.UnionWith(currentNode.ChildrenID);
                return;
            }
            //foreach (int childID in currentNode.GetChildrentID()) {
            // foreach (LatticeNode child in currentNode.Child) {
            for (int childIndex = 0; childIndex < currentNode.Child.Count; childIndex++) {
                LatticeNode child = currentNode.Child[childIndex];
                if (child == n) { continue; }
                //if (childID == n.ID) { continue; }
                //if (checkedItem.Contains(childID)) {
                //    checkedItem = checkedItem.UnionWith(L.Concepts[childID].ChildrenID);
                //    continue;
                //}
                if (checkedItem.Contains(child)) {
                    checkedItem.AddRange(child.Child);
                }
                //Concept child = L.Concepts[childID];
                //if (child.Items.IsSuperSetOf(n.Items)) {
                if (child.SubSet(n) == SubSetRes.SUPSET) {
                    n.AddChild(child);
                    //checkedItem.AddUnique(childID);
                    //checkedItem = checkedItem.UnionWith(child.ChildrenID);
                    checkedItem.Add(child);
                    checkedItem.AddRange(child.Child);
                    if (tidCount == 1) {
                        isFind = true;
                        return;
                    }
                } else {
                    Case3_1_FindChildOfNInDescendantsOfFi(n, child, tidCount, ref isFind, checkedItem);
                }
            }
        }

        #endregion

        #region Case 2
        private void Case2(LatticeNode n, LatticeNode fi, int i, ref bool isAdded, int sup, MaximalTest maximal) {
            if (!isAdded) {
                //L.AddConcept(n);
                maximal.lattice.Add(n);
                isAdded = true;
            }

            //    if (!isAdded) {
            //        L.AddConcept(n);
            //        isAdded = true;
            //    }

            //Fi is the child of N and First Node Fi corresponding to i in In is set to N.
            n.AddChild(fi);
            FirstNodes.UpdateIndexIfExisted(i, n, fi);

            List<LatticeNode> checkedConceptIds = new List<LatticeNode>();
            Case2_FindParentOfNInAncestorsFi(n, fi, checkedConceptIds);
        }

        private void Case2_FindParentOfNInAncestorsFi(LatticeNode n, LatticeNode fi, List<LatticeNode> checkedConceptIds) {
            //foreach (int parentID in fi.GetParentID())
            //foreach (LatticeNode parent in fi.Parent) {
            for (int parentIndex = 0; parentIndex < fi.Parent.Count; parentIndex++) {

                LatticeNode parent = fi.Parent[parentIndex];
                if (n == parent) { continue; }

                //if (n.ID == parentID) { continue; }

                if (checkedConceptIds.Contains(parent)) {
                    checkedConceptIds.AddRange(parent.Parent);
                }
                //if (checkedConceptIds.Contains(parentID))
                //{
                //    checkedConceptIds = checkedConceptIds.UnionWith(L.Concepts[parentID].ParentID);
                //    continue;
                //}

                if (parent.SubSet(n) == SubSetRes.SUBSET) {
                    //if (parent.Items.IsSubSetOf(n.Items))
                    //{

                    bool nochildOfParentIsSuperSet = true;
                    //    foreach (int childOfParentID in parent.Parent)
                    //foreach (LatticeNode childOfParent in parent.Parent) {
                    for (int childOfParentIndex = 0; childOfParentIndex < parent.Child.Count; childOfParentIndex++) {

                        LatticeNode childOfParent = parent.Child[childOfParentIndex];
                        //        if (n.ID == childOfParentID) { continue; }
                        if (n == childOfParent) { continue; }

                        //        if (checkedConceptIds.Contains(childOfParentID))
                        //        {
                        //            checkedConceptIds = checkedConceptIds.UnionWith(L.Concepts[childOfParentID].ParentID);
                        //            continue;
                        //        }
                        if (checkedConceptIds.Contains(childOfParent)) {
                            checkedConceptIds.AddRange(childOfParent.Parent);
                            continue;
                        }
                        //        Concept childOfParent = L.Concepts[childOfParentID];
                        //        if (childOfParent.Items.IsSubSetOf(n.Items))
                        //        {
                        //            nochildOfParentIsSuperSet = false;

                        //            break;
                        //        }
                        SubSetRes childOfParentAndN = childOfParent.SubSet(n);
                        if (childOfParentAndN == SubSetRes.SUBSET) {
                            nochildOfParentIsSuperSet = false;
                            break;
                        } else {
                            if (childOfParentAndN == SubSetRes.SUPSET) {
                                childOfParent.RemoveParentBiDirection(parent);
                                childOfParentIndex--;
                                n.AddChild(childOfParent);
                                parent.AddChild(n);
                                checkedConceptIds.Add(parent);
                                checkedConceptIds.Add(childOfParent);
                                //checkedConceptIds.Add(parent);
                            }
                        }
                        //        else
                        //            if (childOfParent.Items.IsSuperSetOf(n.Items))
                        //            {
                        //                childOfParent.RemoveParent(parent);
                        //                childOfParent.AddParent(n);
                        //                n.AddParent(parent);
                        //                checkedConceptIds.AddUnique(parent.ID);
                        //                checkedConceptIds.AddUnique(childOfParent.ID);
                        //                checkedConceptIds.Add(parent.ID);
                        //            }
                        //    }

                        if (nochildOfParentIsSuperSet) {
                            //=> child is subset of N
                            parent.AddChild(n);
                            checkedConceptIds.Add(parent);
                            checkedConceptIds.AddRange(parent.Parent);
                        } else {
                            Case2_FindParentOfNInAncestorsFi(n, parent, checkedConceptIds);

                        }
                        //    if (nochildOfParentIsSuperSet)
                        //    {
                        //        //=> child is subset of N
                        //        n.AddParent(parent);
                        //        checkedConceptIds.AddUnique(parent.ID);
                        //        checkedConceptIds = checkedConceptIds.UnionWith(parent.ParentID);
                        //    }
                        //    else
                        //    {
                        //        Case2_FindParentOfNInAncestorsFi(n, parent, checkedConceptIds);
                        //        //Case3_2_2_FindChildAndParentOfXInAncestorFi(n, parent, checkedConceptIds);
                        //    }
                    }

                }
            }
        }
        #endregion

        #region Case 1 - New
        private void Case1(LatticeNode n, LatticeNode fi, ref bool isAdded, int tidCount, MaximalTest maximal) {
            //find child and parents of N among the descendants of fi

            if (!isAdded) {
                //L.AddConcept(n);
                maximal.lattice.Add(n);
                isAdded = true;
            }
            n.Sup = tidCount;
            if (fi.Child.Count > 0) {
                //foreach (var x in fi.Child) {
                for (int xIndex = 0; xIndex < fi.Child.Count; xIndex++) {

                    LatticeNode x = fi.Child[xIndex];
                    // if (xID == n.ID) { continue; }
                    SubSetRes res = x.SubSet(n);
                    if (res == SubSetRes.EQUAL) {
                        continue;
                    }

                    if (res == SubSetRes.SUPSET) {
                        fi.AddChild(n);
                        n.AddChild(x);
                        n.Sup = x.Sup + 1;
                        fi.RemoveChildBiDirection(x);
                        xIndex--;
                    }
                }
                List<LatticeNode> checkedConceptIds = new List<LatticeNode>();
                List<LatticeNode> notParentIds = new List<LatticeNode>();
                List<LatticeNode> notChildIds = new List<LatticeNode>();
                bool isFind = false;
                Case1_FindParentOfNInDescendantsFi(n, fi, checkedConceptIds, notParentIds, notChildIds, tidCount, maximal, ref isFind);
            } else {
                fi.AddChild(n);
            }

        }

        private void Case1_FindParentOfNInDescendantsFi(LatticeNode n, LatticeNode currentNode,
            List<LatticeNode> checkedConceptIds, List<LatticeNode> notParentIds,
            List<LatticeNode> notChildIds, int tidCount, MaximalTest maximal, ref bool isFind) {
            //if (isFind || checkedConceptIds.Contains(currentNode.ID)) { return; }
            //foreach (int childID in currentNode.GetChildrentID()) {
            if (isFind || checkedConceptIds.Contains(currentNode)) { return; }
            // foreach (LatticeNode child in currentNode.Child) {
            for (int childIndex = 0; childIndex < currentNode.Child.Count; childIndex++) {
                LatticeNode child = currentNode.Child[childIndex];

                // if (checkedConceptIds.Contains(childID) || n.ID == childID) { continue; }
                if (checkedConceptIds.Contains(child) || n == child) { continue; }
                //Concept child = L.Concepts[childID];
                bool isInNotParent = notParentIds.Contains(child);
                if (isInNotParent) {
                    //notParentIds = notParentIds.UnionWith(child.ParentID);
                    notParentIds.AddRange(child.Parent);
                }

                bool isSubSet = (child.SubSet(n) == SubSetRes.SUBSET);
                //bool isSubSet = child.Items.IsSubSetOf(n.Items);
                if (!isInNotParent && isSubSet) {
                    #region Check is parent

                    bool noChildOfChildIsSubSet = true;
                    bool needLoop = true;
                    // foreach (int childOfChildID in child.GetChildrentID()) {
                    //foreach (LatticeNode childOfChild in child.Child) {
                    for (int childOfChildIndex = 0; childOfChildIndex < child.Child.Count; childOfChildIndex++) {

                        LatticeNode childOfChild = child.Child[childOfChildIndex];
                        //if (n.ID == childOfChildID) { continue; }

                        if (n == childOfChild) { continue; }
                        //Concept childOfChild = L.Concepts[childOfChildID];
                        if (notParentIds.Contains(childOfChild)) {
                            // notParentIds = notParentIds.UnionWith(childOfChild.ParentID);
                            notParentIds.AddRange(childOfChild.Parent);
                            continue;
                        }


                        //if (childOfChild.Items.IsSubSetOf(n.Items)) {

                        SubSetRes subSetResChildOfChildAndN = childOfChild.SubSet(n);

                        //if (childOfChild.SubSet(n) == SubSetRes.SUBSET) {
                        if (subSetResChildOfChildAndN == SubSetRes.SUBSET) {
                            noChildOfChildIsSubSet = false;

                            //notParentIds.AddUnique(childID);
                            notParentIds.Add(child);

                            break;
                        } else {
                            bool isInNotChild1 = notChildIds.Contains(childOfChild);
                            if (isInNotChild1) {
                                //notChildIds = notChildIds.UnionWith(childOfChild.ParentID);
                                notChildIds.AddRange(childOfChild.Parent);
                            }

                            //if (!isInNotChild1 && childOfChild.SubSet(n) == SubSetRes.SUPSET) {
                            if (!isInNotChild1 && subSetResChildOfChildAndN == SubSetRes.SUPSET) {
                                //childOfChild.Items.IsSuperSetOf(n.Items)) {
                                //remove connection between child and childOfChild
                                child.RemoveChildBiDirection(childOfChild);
                                childOfChildIndex--;
                                //child.AddChild(n);
                                n.AddChild(childOfChild);
                                //n found child => didn't need to loop to child of child;
                                needLoop = false;

                                //checkedConceptIds.AddUnique(childOfChild.ID);
                                checkedConceptIds.Add(childOfChild);
                                checkedConceptIds.Add(child);
                                //checkedConceptIds.AddUnique(childID);
                            }
                        }

                    }
                    if (noChildOfChildIsSubSet) {
                        //=> child is parent of N
                        child.AddChild(n);


                        //notChildIds = notChildIds.UnionWith(child.ParentID);
                        notChildIds.AddRange(child.Parent);
                        //notChildIds.AddUnique(childID);
                        notChildIds.Add(child);

                        //notParentIds = notParentIds.UnionWith(child.ParentID);
                        //notParentIds.AddUnique(childID);
                        notParentIds.AddRange(child.Parent);
                        notParentIds.Add(child);
                        //checkedConceptIds.AddUnique(child.ID);
                        checkedConceptIds.Add(child);
                    }
                    if (needLoop) {
                        Case1_FindParentOfNInDescendantsFi(n, child, checkedConceptIds, notParentIds, notChildIds, tidCount, maximal, ref isFind);
                    }
                    #endregion
                }
                //bool isSuperSet = child.Items.IsSuperSetOf(n.Items);
                bool isSuperSet = (child.SubSet(n) == SubSetRes.SUPSET);
                //bool isInNotChild = notChildIds.Contains(childID);
                bool isInNotChild = notChildIds.Contains(child);
                if (isInNotChild) {
                    //notChildIds = notChildIds.UnionWith(child.ChildrenID);
                    notChildIds.AddRange(child.Child);
                }
                if (!isInNotChild && isSuperSet) { //child.SubSet(n) == SubSetRes.SUPSET) { // child.Items.IsSuperSetOf(n.Items)) {

                    n.AddChild(child);
                    //notChildIds = notChildIds.UnionWith(child.ChildrenID);
                    notChildIds.AddRange(child.Child);
                    notChildIds.Add(child);
                    //notChildIds.AddUnique(childID);

                    //notParentIds = notParentIds.UnionWith(child.ChildrenID);
                    //notParentIds.AddUnique(childID);
                    notParentIds.AddRange(child.Child);
                    notParentIds.Add(child);
                    //checkedConceptIds.AddUnique(child.ID);
                    //foreach (int parentOfChildID in child.GetParentID()) {
                    // foreach (LatticeNode parentOfChild in child.Parent) {
                    for (int parentOfChildIndex = 0; parentOfChildIndex < child.Parent.Count; parentOfChildIndex++) {

                        LatticeNode parentOfChild = child.Parent[parentOfChildIndex];
                        if (n == parentOfChild) { continue; }
                        //Concept parentOfChild = L.Concepts[parentOfChildID];

                        bool isNotInParent1 = notParentIds.Contains(parentOfChild);
                        if (isNotInParent1) {
                            //notParentIds = notParentIds.UnionWith(parentOfChild.ChildrenID);
                            notParentIds.AddRange(parentOfChild.Child);
                        }
                        if (!isNotInParent1 && parentOfChild.Items.IsSubSetOf(n.Items)) {
                            parentOfChild.RemoveChildBiDirection(child);
                            parentOfChild.AddChild(n);
                            n.AddChild(child);
                            //checkedConceptIds.AddUnique(child.ID);
                            //checkedConceptIds.AddUnique(parentOfChild.ID);
                            //checkedConceptIds.Add(child);
                            checkedConceptIds.Add(parentOfChild);
                        }
                    }
                    checkedConceptIds.Add(child);
                    if (tidCount == 1) { isFind = true; return; }
                }
                if (!isSuperSet && !isSubSet) {
                    //truong hop cua ab ne
                    LatticeNode newNode = new LatticeNode();
                    newNode.Items = n.Items.IntersectWith(child.Items);

                    LatticeNode existedNode = ItemSetIsExistedInLattice(newNode.Items);
                    if (newNode.Items.Count > 0 && existedNode == null) {

                        //AddTransaction(child.Sup, newNode.Items, maximal);

                        child.RemoveParentBiDirection(currentNode);
                        //childIndex--;
                        newNode.AddChild(n);
                        newNode.AddChild(child);
                        newNode.Sup = n.Sup > child.Sup ? n.Sup : child.Sup;
                        currentNode.AddChild(newNode);
                        maximal.lattice.Add(newNode);
                        checkedConceptIds.Add(newNode);
                    } else if (existedNode != null) {
                        existedNode.AddChild(n);
                        //n.AddParent(existedNode);
                        //checkedConceptIds.AddUnique(existedNode.ID);
                        checkedConceptIds.Add(existedNode);
                    }

                }
            }
        }
        #endregion

        internal LatticeNode ItemSetIsExistedInLattice(List<int> itemSet) {
            foreach (int itemID in itemSet) {
                if (FirstNodes.Indexs.ContainsKey(itemID)) {

                    //int conceptID = FirstNodes.Indexs[itemID];
                    //if (L.Concepts.ContainsKey(conceptID)) {
                    //    Concept curConcept = L.Concepts[conceptID];
                    //    if (curConcept.Items.IsEqual(itemSet)) {
                    //        return L.Concepts[conceptID];

                    //    }
                    //}
                    //int id = -1;
                    //check current node
                    //LatticeNode curNode = FirstNodes.Indexs[itemID];
                    //if (curNode.Items.IsEqual(itemSet)) {
                    //    return curNode;
                    //}

                    return FindItemInDescendants(FirstNodes.Indexs[itemID], itemSet);
                    //if (id != -1 && L.Concepts.ContainsKey(id)) {
                    //    return L.Concepts[id];
                    //}
                }
            }
            return null;
        }

        private LatticeNode FindItemInDescendants(LatticeNode curNode, List<int> itemSet) {
            //LatticeNode curNode = FirstNodes.Indexs[itemID];
            if (curNode != null) {
                if (curNode.Items.IsEqual(itemSet)) {
                    return curNode;
                }


                foreach (var item in curNode.Child) {
                    LatticeNode temp = FindItemInDescendants(item, itemSet);
                    if (temp != null) {
                        return temp;
                    }
                }
            }
            return null;
        }


    }
}
